package 算法.线性表;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author: 谢君臣
 * @create: 2020-12-26 15:42
 * @founction: 非递归实现快速排序
 *    定义一个栈：用于存储每次需要排序的部分；
 *              1. 将待排序的部分压入栈中。
 *              2. 判断栈是否为空
 *                  1. 出栈待排序的部分，进行快排；
 *                  2. 判断返回未知前后两部分长度是否大于1；
 *                      分别将大于1的部分继续压入栈中。
 */
public class 快速排序非递归 {
    public static int[] array;

    public static void main(String[] args) {
        Stack<part> stack = new Stack<>();
        array = new int[]{6, 3, 0, 9, 2, 11, 7, 5, 1, 8, 4, 10};
        part part = new part(0, array.length - 1);
        stack.push(part);
        while (!stack.empty()) {
            part p = stack.pop();
            int mid = quickSort(array, p.getStart(), p.getEnd()); // 快速排序，返回中间位置
            if (mid - p.start > 1) { // 判断前面的部分长度大于1
                stack.push(new part(p.start, mid - 1)); // 压入待排序的部分
            }
            if (p.end - mid > 1) { // 判断后面的部分长度大于1
                stack.push(new part(mid + 1, p.end)); // 压入待排序的部分
            }
            System.out.println(Arrays.toString(array)); // 每次输出快排序的结果
        }
    }

    private static int quickSort(int[] array, int i, int j) {
        int temp = array[i],low = i;
        while (i < j) {
            /**
             *  如果以第一个元素为基准，必选先算 j--
             */
            while (array[j] >= temp && i < j) {
                j--;
            }
            while (array[i] <= temp && i < j) {
                i++;
            }
            if (i != j)
                swap(array, i, j);
        }
        swap(array, low, i); // 不能省略
        return i;
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    static class part {
        int start;
        int end;

        public part(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }
    }
}
